package com.lw.leetcode.arr.c;

import com.lw.test.util.Utils;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * arr
 * 面试题 17.24. 最大子矩阵
 *
 * @author liw
 * @version 1.0
 * @date 2022/9/27 16:05
 */
public class GetMaxMatrix {

    public static void main(String[] args) {
        GetMaxMatrix test = new GetMaxMatrix();
        // [[9,-8,1,3,-2],
        // [-3,7,6,-2,4],
        // [6,-4,-4,8,-7]]
        //

        // [0,1,0,1]
//        int[][] arr = {{-1, 0}, {0, -1}};

        // [0,0,2,3]
//        int[][] arr = {{9, -8, 1, 3, -2}, {-3, 7, 6, -2, 4}, {6, -4, -4, 8, -7}};

        int[][] arr = Utils.getArr(200, 200, 0, 1000);

        int[] maxMatrix = test.getMaxMatrix(arr);
        System.out.println(Arrays.toString(maxMatrix));

    }

    public int[] getMaxMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][][] items = new int[m][m][n];
        int[][][] items2 = new int[m][m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0) {
                    if (j == 0) {
                        continue;
                    }
                    matrix[i][j] += matrix[i][j - 1];
                } else if (j == 0) {
                    matrix[i][j] += matrix[i - 1][j];
                } else {
                    matrix[i][j] += (matrix[i - 1][j] + matrix[i][j - 1] - matrix[i - 1][j - 1]);
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j <= i; j++) {
                int sum = 0;
                int y = 0;
                for (int k = 1; k < n; k++) {
                    int t = matrix[i][k - 1];
                    if (j != 0) {
                        t -= matrix[j - 1][k - 1];
                    }
                    if (t < sum) {
                        sum = t;
                        y = k;
                    }
                    items[i][j][k] = sum;
                    items2[i][j][k] = y;
                }
            }
        }
        int max = Integer.MIN_VALUE;
        int[] values = new int[4];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k <= i; k++) {
                    int t = matrix[i][j];
                    if (k != 0) {
                        t -= matrix[k - 1][j];
                    }
                    t = t - items[i][k][j];
                    if (t > max) {
                        max = t;
                        values[0] = k;
                        values[1] = items2[i][k][j];
                        values[2] = i;
                        values[3] = j;
                    }
                }
            }
        }
        return values;
    }

}
